# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


def print_list(l1):
    while l1:
        print l1.val
        l1 = l1.next


class Solution(object):
    def addTwoNumbers(self, l1, l2):
        ax = 0
        res_val = 0

        res = ListNode(None)
        _res = res

        while True:
            if l1 is None:
                if l2 is None:
                    break

                else:
                    res_val = ax + l2.val
                    ax = 0
                    if res_val >= 10:
                        ax = 1
                        res_val = res_val - 10

                    res_new_node = ListNode(res_val)
                    if res.val is not None:
                        res.next = res_new_node
                        res = res.next
                    else:
                        res.val = res_new_node.val

                    l2 = l2.next

            elif l2 is None:
                if l1 is None:
                    break

                else:
                    res_val = ax + l1.val
                    ax = 0
                    if res_val >= 10:
                        ax = 1
                        res_val = res_val - 10

                    res_new_node = ListNode(res_val)
                    if res.val is not None:
                        res.next = res_new_node
                        res = res.next
                    else:
                        res.val = res_new_node.val

                    l1 = l1.next

            else:
                # print "l1.val: %s, l2.val: %s" % (l1.val, l2.val)

                res_val = l1.val + l2.val + ax
                ax = 0
                if res_val >= 10:
                    ax = 1
                    res_val = res_val - 10

                res_new_node = ListNode(res_val)
                if res.val is not None:
                    res.next = res_new_node
                    res = res.next

                else:
                    res.val = res_new_node.val

                l1 = l1.next
                l2 = l2.next

        if ax != 0:
            res.next = ListNode(ax)

        return _res

if __name__ == "__main__":
    sol = Solution()

    l1 = ListNode(9)
    _l1 = l1
    l1.next = ListNode(9)

    l2 = ListNode(1)
    _l2 = l2

    print_list(sol.addTwoNumbers(_l1, _l2))
